package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;

public class LongestValidParentheses {

    /**
     * 利用栈来存储来存储左括号的下标，如果遇到右括号，此时假如栈为空，弹出上一个左括号的下标，否则加入右括号的下标。
     * 最终遍历完字符串，栈剩下的就是无效的括号的下标，此时每个下标之间的都是有效的括号，遍历栈即可以得到最长有效括号的长度
     */
    public int longestValidParentheses1(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if (c == '('){
                stack.addLast(i);
                count++;
            } else {
                count--;
                if (count >= 0){
                    stack.removeLast();
                } else {
                    stack.addLast(i);
                    count = 0;
                }
            }
        }
        stack.addLast(s.length());
        int max = 0;
        int m = -1;
        for (int n: stack){
            int len = n - m - 1;
            if (max < len){
                max = len;
            }
            m = n;
        }
        return max;
    }

    /**
     * 动态规划。
     * 下标i所在的字符有以下多种情况：
     * 1. 是左括号，有效长度记为0
     * 2. 是右括号，并且正好前一个字符为左括号，满足’()‘形式，此时 dp[i] = dp[i - 2] + 2
     * 3. 是右括号，并且满足'(...)'的形式，’（‘处于 i - dp[i - 1] - 1 的位置， 此时 dp[i] = dp[i - 1] + 2
     * 4. 其他情况记为0
     * 举例说明：
     *  s = (()())
     *  所以 dp[2] = dp[0] + 2 = 2;
     *      dp[4] = dp[2] + 2 = 4;
     *      dp[5] = dp[4] + 2 = 6
     */
    public int longestValidParentheses(String s) {
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); ++i){
            char c = s.charAt(i);
            System.out.println(c);
            if (c == ')'){
                if (s.charAt(i - 1) == '('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] >= 1 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        String s= "(()())";
        int i = new LongestValidParentheses().longestValidParentheses(s);
        int i1 = new LongestValidParentheses().longestValidParentheses1(s);
        PrintUtils.println(i, i1);
    }

}
